{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Petroleum Blending (Solved)\n", "## Problem Definition\n", "Harry Stamper is an engineer working on a petroleum company. The company produces three grades of motor oil – super, premium, and extra. The three grades are made from the same 3 ingredients, named component 1, component 2 and component 3. The company wants to determine the optimal mix of the 3 components in each grade of motor oil that will maximize profit. \n", "\n", "The maximum availability of each component and their cost per barrel are as follows:\n", "\n", "| Component | Max barrels available / day | Cost / barrel |\n", "|--------------|------------------------------|---------------|\n", "| Component 1 | 4.500 | 12€ |\n", "| Component 2 | 2.700 | 10€ |\n", "| Component 3 | 3.500 | 14€ |\n", "\n", "To ensure the appropriate blend, each grade must have a minimum amount of component 1 plus a combination of other components as follows:\n", "\n", "| Grade | Component 1 | Component 2 | Component 3 | Selling price/barrel |\n", "|---------|--------------|------------------|------------------|----------------------|\n", "| Super | At least 50% | No more than 30% | - | 23€ |\n", "| Premium | At least 40% | - | No more than 25% | 20€ |\n", "| Extra | At least 60% | At least 10% | - | 18€ |\n", "\n", "The company wants to make at least 3000 barrels of each blend.\n", "*Formulate an LP to help Harry Stamper find the optimal blend that maximises profit.*" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Problem Model\n", "The decision variables are: \n", "\n", "$x_{ij}$ = amount in barrels of component i in grade j\n", "\n", "Objective function\n", "\n", "max $z = 23*(x_{11} + x_{21} + x_{31}) + 20*(x_{12} + x_{22} + x_{32})+18*(x_{13} + x_{23} + x_{33})-12*(x_{11} + x_{12} + x_{13}) - 10*(x_{21} + x_{22} + x_{23})-14*(x_{31} + x_{32} + x_{33})$\n", "\n", "Constraints\n", "\n", "$x_{11} \\geq 0.5*(x_{11} + x_{21} + x_{31})$ Component 1 requirement in Super\n", "\n", "$x_{21} \\leq 0.3*(x_{11} + x_{21} + x_{31})$ Component 2 requirement in Super\n", "\n", "$x_{12} \\geq 0.4*(x_{12} + x_{22} + x_{32})$ Component 1 requirement in Premium\n", "\n", "$x_{32} \\leq 0.25*(x_{12} + x_{22} + x_{32})$ Component 3 requirement in Premium\n", "\n", "$x_{13} \\geq 0.6*(x_{13} + x_{23} + x_{33})$ Component 1 requirement in Extra\n", "\n", "$x_{23} \\geq 0.1*(x_{13} + x_{23} + x_{33})$ Component 2 requirement in Extra\n", "\n", "\n", "$x_{11}+x_{12}+x_{13} \\leq 4500$ Component 1 availability\n", "\n", "$x_{21}+x_{22}+x_{23} \\leq 2700$ Component 1 availability\n", "\n", "$x_{31}+x_{32}+x_{33} \\leq 3500$ Component 1 availability\n", "\n", "$x_{11}+x_{21}+x_{31} \\geq 3000$ Super minimum production\n", "\n", "$x_{12}+x_{22}+x_{32} \\geq 3000$ Premium minimum production\n", "\n", "$x_{13}+x_{23}+x_{33} \\geq 3000$ Extra minimum production" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Analysis questions**\n", "\n", "This is the solution of the problem obtained with Gurobi solver in [Petroleum Blending (Solved CBC)](Petroleum%20Blending%20(Solved%20CBC).ipynb):\n", "\n", "**Decision Variables**\n", "\n", "| | Variables | Solution \\(GRB\\) | Reduced cost \\(GRB\\) | Objective Coefficient \\(GRB\\) | Objective Lower bound \\(GRB\\) | Objective Upper bound \\(GRB\\) |\n", "|:-------------------------|:------------------------------------------------------|:-----------------|:---------------------|:------------------------------|:------------------------------|:------------------------------|\n", "| \\(Super, Component 1\\) | Quantity\\_in\\_barrels\\_\\('Super',\\_'Component\\_1'\\) | 1500.000 | 0.000 | 11.000 | 8.000 | Inf |\n", "| \\(Super, Component 2\\) | Quantity\\_in\\_barrels\\_\\('Super',\\_'Component\\_2'\\) | 450.000 | 0.000 | 13.000 | 13.000 | 13.000 |\n", "| \\(Super, Component 3\\) | Quantity\\_in\\_barrels\\_\\('Super',\\_'Component\\_3'\\) | 1050.000 | 0.000 | 9.000 | 9.000 | 9.000 |\n", "| \\(Premium, Component 1\\) | Quantity\\_in\\_barrels\\_\\('Premium',\\_'Component\\_1'\\) | 1200.000 | 0.000 | 8.000 | -Inf | 11.000 |\n", "| \\(Premium, Component 2\\) | Quantity\\_in\\_barrels\\_\\('Premium',\\_'Component\\_2'\\) | 1050.000 | 0.000 | 10.000 | -Inf | 10.000 |\n", "| \\(Premium, Component 3\\) | Quantity\\_in\\_barrels\\_\\('Premium',\\_'Component\\_3'\\) | 750.000 | 0.000 | 6.000 | 6.000 | 10.800 |\n", "| \\(Extra, Component 1\\) | Quantity\\_in\\_barrels\\_\\('Extra',\\_'Component\\_1'\\) | 1800.000 | 0.000 | 6.000 | -Inf | 17.333 |\n", "| \\(Extra, Component 2\\) | Quantity\\_in\\_barrels\\_\\('Extra',\\_'Component\\_2'\\) | 1200.000 | 0.000 | 8.000 | 8.000 | 25.000 |\n", "| \\(Extra, Component 3\\) | Quantity\\_in\\_barrels\\_\\('Extra',\\_'Component\\_3'\\) | 0.000 | -0.000 | 4.000 | -Inf | 4.000 |\n", "\n", "\n", "**Constraints**\n", "\n", "| idx | Constraint | Right Hand Side | Shadow Price | Slack | Min RHS | Max RHS |\n", "|:----|:---------------------------------------|:----------------|:-------------|:--------|:--------|:--------|\n", "| 0 | Component\\_1\\_requirement\\_in\\_super | 0.00 | -18.00 | 0.00 | -850.00 | 0.00 |\n", "| 1 | Component\\_2\\_requirement\\_in\\_super | 0.00 | 0.00 | 450.00 | -450.00 | Inf |\n", "| 2 | Component\\_1\\_requirement\\_in\\_premium | 0.00 | -18.00 | 0.00 | -450.00 | 0.00 |\n", "| 3 | Component\\_3\\_requirement\\_in\\_premium | 0.00 | 0.00 | 0.00 | -450.00 | 450.00 |\n", "| 4 | Component\\_1\\_requirement\\_in\\_Extra | 0.00 | -18.00 | 0.00 | -450.00 | 0.00 |\n", "| 5 | Component\\_2\\_requirement\\_in\\_Extra | 0.00 | 0.00 | -900.00 | -Inf | 900.00 |\n", "| 6 | Component\\_1\\_availability | 4500.00 | 20.00 | 0.00 | 4500.00 | 6200.00 |\n", "| 7 | Component\\_2\\_availability | 2700.00 | 4.00 | 0.00 | 2250.00 | 3150.00 |\n", "| 8 | Component\\_3\\_availability | 3500.00 | 0.00 | 1700.00 | 1800.00 | Inf |\n", "| 9 | Super\\_minimum\\_production | 3000.00 | 0.00 | -0.00 | -Inf | 3000.00 |\n", "| 10 | Premium\\_minimum\\_production | 3000.00 | -1.20 | 0.00 | -0.00 | 3000.00 |\n", "\n", "\n", "\n", "* Which is the total profit obtained by the company with the Extra grade with the solution provided by the solver?\n", "\n", "Just multiply the value of every basic (non-zero) decision variable times the objective function coefficient. \n", "\n", "* Which is the maximum value that the profit per barrel of component 2 in the Extra grade can take without changing the base of the optimal solution?\n", "\n", "The profit per barrel of component two in the extra grade is 8.00 (look at the second last row of the first table). The maximum value that it can take is the upper bound of the objective function in that row, which is 25. The profit per barrel of component 2 could change from 8.00 to 25 without changing the base. Since there are no changes in the constraint, there are no changes in the feasible region and the optimal solution will be the same point and same quantities. Therefore, if we were able to raise the profit by 1 eur per barrel of component 2 in extra grade, the total profit (objective function) will increase 12000 (because this is the quantity of this component in the extra grade in the optimal solution).\n", "\n", "* If the cost of the barrel of component 3 increased 1€, will the optimal composition change? Motivate your response\n", "\n", "In this case an increase of the cost of barrel of component 3 means that the profit per component 3 in the three grades is going to decrease by 1 eur. Since the lower bound of the profit per component 3 in the “Super” grade is equal to the objective function coefficient, there will be a change in the optimal composition. \n", "\n", "\n", "* Do we use every barrel available of every component in the optimal solution? Or do we have any surplus availability for any component? Motivate your response\n", "\n", "If we look at the components availability, we can clearly see that we have a slack of 1700 barrels of component 3.\n", "\n", "\n", "* The provider of Component 2 may have a problem with the delivery and the availability may be reduced in 400 barrels. Will this shortage affect the optimal composition? Motivate your response*\n", "\n", "If the component 2 is short in 4000 barrels (from 2700 to 2300) the availability will still be higher than the lower bound of the component 2 available constraint which is 2250, so this shortage in principle will not affect the optimal solution.\n", "\n", "* Grace wants to use the results to renegotiate the terms and conditions with the suppliers of the different components. Which component is a better candidate to increase the availability? How would you use the model to negotiate new terms with the provider, assuming you do not want any change in the base of the optimal solution? Motivate your response\n", "\n", "Now, this is a quite an interesting question. If we were to increase the availability, we can first discard component 3, because we have the aforementioned slack, which means that we are not using all the available material, so the candidates are component 1 and 2. Now, comparing both components, component 1 has a much larger shadow price, which means that for every change of one unit on the right hand side, we will have an increase of 20 eur in the profit. So this is definitively the best candidate. We could try to negotiate the terms and conditions and try to tell the provider that we want more units of this component. We could use up to 6200 units (upper right hand side) without changes in the optimal composition. Now, since we are buying more units, we may as well ask for a lower price. If we look at the profits of component 1 in the first table, we could increase the profits of Premium, component 1 by 3 euros (from 8 to 11 which is the upper bound) so we could try to renegotiate the price from 12 down to 9. " ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.7.4" }, "pycharm": { "stem_cell": { "cell_type": "raw", "source": [], "metadata": { "collapsed": false } } } }, "nbformat": 4, "nbformat_minor": 2 }